<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>找到所有好字符串</title>
</head>
<body>
  <script>
    function fn(n, s1, s2, evil) {
      const m = evil.length;
      const mod = 1e9 + 7;
      const evilNext = getNext(evil);
      const getNum = (str) => {
        const map = new Map();
        const dfs = (index, isLimit, hit) => {
          const key = [index, isLimit, hit].join(',');
          if (map.has(key)) {
            return map.get(key);
          }
          if (hit === m) {
            return 0;
          }
          if (index === n) {
            return 1;
          }
          let res = 0;
          for (let i = 97, up = isLimit ? str[index].charCodeAt() : 122; i <= up; i++) {
            const cur = String.fromCharCode(i);
            let nextHit = hit;
            while (nextHit !== 0 && cur !== evil[nextHit]) {
              nextHit = evilNext[nextHit - 1];
            }
            if (cur === evil[nextHit]) {
              nextHit++;
            }
            res += dfs(index + 1, isLimit && i === up, nextHit);
            res %= mod;
          }
          map.set(key, res);
          return res;
        }
        return dfs(0, true, 0);
      }
      function getNext(needle) {
        let j = 0, len = needle.length;
        let next = new Array(len).fill(0);
        for (let i = 1; i < len; i++) {
          while (j !== 0 && needle[i] !== needle[j]) {
            j = next[j - 1]
          }
          if (needle[i] === needle[j]) {
            j++;
          }
          next[i] = j;
        }
        return next;
      }
      return (getNum(s2) - getNum(s1) + Number(s1.indexOf(evil) === -1) + mod) % mod;
    }
    console.log(fn(2, 'aa', 'da', 'b'))
  </script>
</body>
</html>